#include <vector>
#include <string>
#include <fstream>
#include <algorithm>
#include <iostream>

namespace part2
{

    using Position = std::pair<std::int64_t, std::int64_t>; 

    std::vector<std::string> readImage();
    std::vector<std::size_t> emptyRowsIndex(const std::vector<std::string>& image);
    std::vector<std::size_t> emptyColsIndex(const std::vector<std::string>& image);
    std::vector<Position> getGalaxiesPosition(
                          const std::vector<std::string>& image,
                          std::vector<std::size_t> emptyRows,
                          std::vector<std::size_t> emptyCols);
    std::int64_t calculateShortestPath(const std::vector<Position>& galaxies);

    void solute()
    {
        std::vector<std::string> image {readImage()};
        std::vector<std::size_t> emptyRows {emptyRowsIndex(image)};
        std::vector<std::size_t> emptyCols {emptyColsIndex(image)};
        std::vector<Position> galaxies {getGalaxiesPosition(image, emptyRows, emptyCols)};
        std::cout << calculateShortestPath(galaxies) << std::endl;
    }

    std::vector<std::string> readImage()
    {
        std::ifstream infile {"./src/day11/input.txt"};
        std::string line {};
        std::vector<std::string> image {};
        while (std::getline(infile, line))
            image.emplace_back(std::move(line));
        return image;
    }

    std::vector<std::size_t> emptyRowsIndex(const std::vector<std::string>& image)
    {
        std::size_t row {image.size()};
        std::size_t column {image.front().size()};
        std::string emptyLine (column, '.');

        std::vector<std::size_t> emptyRows {};
        for (std::size_t r = 0; r < row; ++r)
        {
            if (emptyLine == image[r])
                emptyRows.emplace_back(r);
        }

        return emptyRows;
    }

    std::vector<std::size_t> emptyColsIndex(const std::vector<std::string>& image)
    {
        std::size_t row {image.size()};
        std::size_t column {image.front().size()};
        std::vector<std::size_t> emptyCols {};

        for (std::size_t c = 0; c < column; ++c)
        {
            bool allEmpty {true};
            for (std::size_t r = 0; r < row; ++r)
            {
                if (image[r][c] != '.')
                {
                    allEmpty = false;
                    break;
                }
            }
            
            if (allEmpty) emptyCols.emplace_back(c);
        }

        return emptyCols;
    }

    std::vector<Position> getGalaxiesPosition(
                          const std::vector<std::string>& image,
                          std::vector<std::size_t> emptyRows,
                          std::vector<std::size_t> emptyCols)
    {
        constexpr std::size_t expandRatio {1000000};

        std::size_t row {image.size()};
        std::size_t column {image.front().size()};
        std::vector<Position> positions {};

        for (std::size_t r = 0; r < row; ++r)
        {
            for (std::size_t c = 0; c < column; ++c)
            {
                if (image[r][c] == '#')
                {
                    std::size_t emptyRowsCount {
                        std::count_if(emptyRows.begin(), emptyRows.end(), [r](std::size_t v){ return v < r; })
                    };
                    std::size_t emptyColsCount {
                        std::count_if(emptyCols.begin(), emptyCols.end(), [c](std::size_t v){ return v < c; })
                    };
                    
                    // Never overflow!
                    std::int64_t realRow {static_cast<std::int64_t>(r + (emptyRowsCount) * (expandRatio - 1))};
                    std::int64_t realCol {static_cast<std::int64_t>(c + (emptyColsCount) * (expandRatio - 1))};

                    positions.emplace_back(realRow, realCol);
                }
            }
        }
        return positions;
    }

    std::int64_t calculateShortestPath(const std::vector<Position>& galaxies)
    {
        // for (const Position& pos : galaxies)
        //     std::cout << "[" << pos.first << ", " << pos.second << ']' << std::endl;

        std::size_t galaxiesSize {galaxies.size()};
        std::vector<std::int64_t> paths {};
        std::int64_t pathSum {0};

        auto absInt = [] (std::int64_t v) -> std::int64_t {
            return v > 0 ? v : -v;
        };
        auto getPath = [&absInt] (const Position& startPos, const Position& endPos) -> std::int64_t {
            std::int64_t absX {absInt(startPos.first - endPos.first)};
            std::int64_t absY {absInt(startPos.second - endPos.second)};
            return absX + absY;
        };

        for (std::size_t s = 0; s < galaxiesSize; ++s)
        {
            for (std::size_t e = 0; e < s; ++e)
            {
                std::int64_t path {getPath(galaxies[s], galaxies[e])};
                paths.emplace_back(path);
                pathSum += path;
            }
        }

        return pathSum;
    }

}